package exercises

object Tree {
  import scala.util.parsing.combinator._

  def hbalTrees[T](height: Int, value: T): List[Tree[T]] = height match {
    case n if n < 1 => List(End)
    case 1 => List(Node(value))
    case _ => {
      val fullHeight = hbalTrees(height - 1, value)
      val short = hbalTrees(height - 2, value)
      fullHeight.flatMap((l) => fullHeight.map((r) => Node(value, l, r))) :::
        fullHeight.flatMap((f) => short.flatMap((s) => List(Node(value, f, s), Node(value, s, f))))
    }
  }

  def fromList[T <% Ordered[T]](list: List[T]): Tree[T] = list.foldLeft(End: Tree[T]) { (t, e) => t.addValue(e) }

  def completeBinaryTree[T](nodes: Int, x: T) = {
    def gen(addr: Int): Tree[T] = if (addr > nodes) End else Node(x, gen(2 * addr), gen(2 * addr + 1))
    gen(1)
  }

  def string2Tree[T](string: String): Tree[Char] = Parser.parse(string).get

  private object Parser extends RegexParsers {
    def value: Parser[Char] = "[a-zA-Z]".r ^^ (x => x.toCharArray()(0))
    def tree: Parser[Tree[Char]] = (value ~ "(" ~ tree ~ "," ~ tree ~ ")" ^^ { case value ~ "(" ~ leftBranch ~ "," ~ rightBranch ~ ")" => (Node(value, leftBranch, rightBranch)) }
      | value ^^ (value => Node(value))
      | "" ^^ (value => End))

    def parse(string: String) = parseAll(tree, string)
  }

  def preInTree[Char](pre: List[Char], in: List[Char]): Tree[Char] = pre match {
    case Nil => End
    case preHead :: preTail => {
      val (leftIn, rightIn) = in.span(_ != preHead)
      Node(preHead, preInTree(preTail.take(leftIn.size), leftIn), preInTree(preTail.drop(leftIn.size), rightIn))
    }
  }

  def fromDotString(string: String): Tree[Char] = {
    def fromDotStringInternal(pos: Int): (Tree[Char], Int) = string(pos) match {
      case '.' => (End, pos + 1)
      case value => {
        val (leftBranch, leftPos) = fromDotStringInternal(pos + 1)
        val (rightBranch, rightPos) = fromDotStringInternal(leftPos)
        (Node(value, leftBranch, rightBranch), rightPos)
      }
    }
    fromDotStringInternal(0)._1
  }
}

sealed abstract class Tree[+T] {
  def isLeaf: Boolean
  def isSymmetric: Boolean
  def isMirrorOf[V](tree: Tree[V]): Boolean
  def addValue[U >: T <% Ordered[U]](x: U): Tree[U]
  def leafCount: Int
  def leafList: List[T]
  def internalList: List[T]
  def atLevel(level: Int): List[T]
  def layoutBinaryTree: Tree[T] = layoutBinaryTreeInternal(1, 0)._1
  def layoutBinaryTreeInternal(level: Int, visited: Int): (Tree[T], Int)
  def height: Int
  //    def layoutBinaryTree2: Tree[T] = layoutBinaryTree2Internal(0, 1, pow(2, height).toInt)._1
  //    def layoutBinaryTree2Internal(x: Int, level: Int, nodesDistance: Int): (Tree[T], Int)
  def preorder: List[T]
  def inorder: List[T]
  def toDotString: String
}

case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = if (isLeaf) value.toString else value + "(" + left.toString + "," + right.toString + ")"
  override def isLeaf = left == End && right == End
  override def isSymmetric = left.isMirrorOf(right)

  override def isMirrorOf[V](tree: Tree[V]): Boolean = tree match {
    case t: Node[V] => left.isMirrorOf(t.left) && right.isMirrorOf(t.right)
    case End => false
  }

  override def addValue[U >: T <% Ordered[U]](x: U): Tree[U] = {
    if (x < value) Node(value, left.addValue(x), right)
    else if (x > value) Node(value, left, right.addValue(x))
    else this
  }

  override def leafCount = (left, right) match {
    case (End, End) => 1
    case _ => left.leafCount + right.leafCount
  }

  override def leafList: List[T] = (left, right) match {
    case (End, End) => List(value)
    case _ => left.leafList ::: right.leafList
  }

  override def internalList: List[T] = (left, right) match {
    case (End, End) => left.internalList ::: right.internalList
    case (_) => value :: left.internalList ::: right.internalList
  }

  override def atLevel(level: Int) = level match {
    case n if n < 1 => Nil
    case 1 => List(value)
    case _ => left.atLevel(level - 1) ::: right.atLevel(level - 1)
  }

  override def layoutBinaryTreeInternal(level: Int, visited: Int) = {
    val (leftBranch, leftAccumVisited) = left.layoutBinaryTreeInternal(level + 1, visited)
    val (rightBranch, rightAccumVisited) = right.layoutBinaryTreeInternal(level + 1, leftAccumVisited + 1)
    (PositionedNode(value, leftBranch, rightBranch, level, leftAccumVisited + 1), rightAccumVisited)
  }

  override def height = left.height max right.height + 1

  //    override def layoutBinaryTree2Internal(x: Int, level: Int, nodesDistance: Int) = {
  //    	val (leftBranch, leftX) = left.layoutBinaryTree2Internal(x, level + 1, nodesDistance / 2)
  //    	val (rightBranch, rightX) = right.layoutBinaryTree2Internal(leftX + nodesDistance / 2, level + 1, nodesDistance / 2)
  //    	val nodeX = leftX + nodesDistance / 4
  //    	(PositionedNode(value, leftBranch, rightBranch, nodeX, level), nodeX)
  //    }

  override def preorder = value :: left.preorder ::: right.preorder
  override def inorder = left.inorder ::: List(value) ::: right.inorder
  override def toDotString = value + left.toDotString + right.toDotString
}

case class PositionedNode[+T](override val value: T, override val left: Tree[T], override val right: Tree[T], x: Int, y: Int) extends Node[T](value, left, right) {
  override def toString = value + "[" + x.toString + "," + y.toString + "]" + (if (!isLeaf) "(" + left.toString + "," + right.toString + ")" else "")
}

case object End extends Tree[Nothing] {
  override def toString = ""
  override def isLeaf = false
  override def isSymmetric = true
  override def isMirrorOf[V](tree: Tree[V]): Boolean = tree == End
  override def addValue[U <% Ordered[U]](x: U): Tree[U] = Node(x)
  override def leafCount = 0
  override def leafList = Nil
  override def internalList = Nil
  override def atLevel(level: Int) = Nil
  override def layoutBinaryTreeInternal(level: Int, visited: Int) = (End, visited)
  override def height = 0
  //    override def layoutBinaryTree2Internal(x: Int, level: Int, nodesDistance: Int) = (End, x - )
  override def preorder = Nil
  override def inorder = Nil
  override def toDotString = "."
}

object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}

// TODO: Esta clase debería estar fuera del paquete tree
object TreeExample extends Application {
  println(Node('a', Node('b'), Node('c')).isSymmetric) // 56
  println(End.addValue('d').addValue('a').addValue('f').addValue('c')) // 57
  println(Tree.fromList(List(5, 3, 18, 1, 4, 12, 21)).isSymmetric) // 57
  println(Tree.fromList(List(3, 2, 5, 7, 4)).isSymmetric) // 57
  println(Tree.hbalTrees(2, "x")) // 59
  println(Node('x', Node('x'), End).leafCount) //61
  println(Node('a', Node('b'), Node('c', Node('d'), Node('e'))).leafList) //61A
  println(Node('a', Node('b'), Node('c', Node('d'), Node('e'))).internalList) //62
  println(Node('a', Node('b'), Node('c', Node('d'), Node('e'))).atLevel(2)) //62B
  println(Tree.completeBinaryTree(6, "x")) //63
  println(Node('a', Node('b', End, Node('c')), Node('d')).layoutBinaryTree) // 64
  println(Tree.fromList(List('n', 'k', 'm', 'c', 'a', 'h', 'g', 'e', 'u', 'p', 's', 'q')).layoutBinaryTree) // 64
  //    println(Tree.fromList(List('n','k','m','c','a','e','d','g','u','p','q')).layoutBinaryTree2) // 65
  val tree = Node('a', Node('b', Node('d'), Node('e')), Node('c', End, Node('f', Node('g'), End))) //67
  println(tree.toString) //67
  println(Tree.string2Tree(tree.toString)) //67
  //        val layoutTree = tree.layoutBinaryTree //67
  //        println(layoutTree) //67
  //        println(Tree.fromString(layoutTree.toString))
  println(Tree.string2Tree("a(b(d,e),c(,f(g,)))").preorder) // 68
  println(Tree.string2Tree("a(b(d,e),c(,f(g,)))").inorder) // 68
  println(Tree.preInTree(List('a', 'b', 'd', 'e', 'c', 'f', 'g'), List('d', 'b', 'e', 'a', 'c', 'g', 'f'))) // 68
  println(Tree.string2Tree("a(b(d,e),c(,f(g,)))").toDotString) // 69
  println(Tree.fromDotString("abd..e..c.fg...")) //69
}
